import java.util.HashMap;
import java.util.Map;

public class project {
    public int jump(int[] nums) {
        int index=0;
        int len=nums.length;
        int ret=0;
        int end=0;
        for(int i=0;i<len-1;i++){
            index=Math.max(index,i+nums[i]);
            if(i==end){
                end=index;
                ret++;
            }
        }
        return ret;
    }












    public boolean canJump(int[] nums) {
        int index=0;
        int len=nums.length;
        if(len<2){
            return true;
        }
        for(int i=0;i<=index;i++){
            index=Math.max(index,i+nums[i]);
            if(index>=len-1){
                return true;
            }
        }
        return false;
    }


















    public int numEnclaves(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int ret=0;
        for(int i=0;i<row;i++){
            dfs(grid,i,0);
            dfs(grid,i,col-1);
        }
        for(int i=0;i<col;i++){
            dfs(grid,0,i);
            dfs(grid,row-1,i);
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    ret++;
                }
            }
        }
        return ret;
    }

    private void dfs(int[][] grid, int x, int y) {
        if(x<0||y<0||x>=grid.length||y>=grid[0].length||grid[x][y]==0){
            return;
        }
        grid[x][y]=0;
        dfs(grid,x+1,y);
        dfs(grid,x-1,y);
        dfs(grid,x,y+1);
        dfs(grid,x,y-1);
    }















    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k<2){
            return 0;
        }
        int ret=0;
        int len=nums.length;
        int left=0;
        int right=0;
        int sum=1;
        while (right<len){
            sum*=nums[right];
            while(sum>=k){
                sum/=nums[left];
                left++;
            }
            ret+=right-left+1;
            right++;
        }
        return ret;
    }
}
